1. Field of the Invention
The invention relates to cryptography and, more particularly, to a system and method for facilitating cryptographic applications.
2. Description of the Prior Art
Key Agreement Protocols
It is sometimes desirable for individuals to be able to communicate with each other in a way in which third parties are unable to listen to the communication. A simple way for these individuals to communicate is to have the communications themselves proceed in private. For example if party A and party B desire to communicate in a way which will not be heard by party C, A and B can simply meet at a designated location unknown to C. Similarly, A and B can set up a designated communication line between them which excludes C. Such communication lines are expensive and inconvenient especially if A and B are geographically far apart from one another.
A first approach to facilitating private communications between A and B is to give A and B a secret key that may be used to encrypt and/or decrypt messages sent between A and B. If C does not know what the key is, it may be very difficult for C to both get a hold of a message sent between A and B and try to understand it. However, giving A and B such a key is also cumbersome, expensive and time consuming. Issues to be addressed include secretly transmitting such a key to A and B and generating a new key each time two individuals need to communicate. Also, if C does ascertain the secret key, then all communications between A and B can be decrypted and read by C.
Another approach for facilitating private communications between A and B is to assign A and B secret mathematical functions ƒa, ƒb respectively. The functions ƒa and ƒb are chosen from a set of functions, S, all of whose elements are designed so as to be commutative: applying ƒa followed by ƒb yields the same result as applying ƒb followed by ƒa (i.e., given an element x, ƒa(ƒb(x))=ƒb(ƒa(x))). Assuming the element x is known by both A and B, A can then send ƒa(x) to B, and B can send ƒb(x) to A over public channels. The secret key that can be evaluated and shared by both A and B is then, ƒa (ƒb(x))=ƒb(ƒa(x)). To insure that the system is secure (from an adversary C who knows x and can listen to all communication between A and B) it is necessary that the functions ƒa and ƒb satisfy the following property: given the value ƒa(x) (respectively ƒb(x)) it is computationally difficult to determine the function ƒa (respectively ƒb). This is called the general Diffie-Hellman key agreement protocol.
Many specific instances of the general Diffie-Hellman protocol for sending secure communications between A and B are known in the prior art (see Alfred J. Menezes, Paul C. van Oorschot, and Scott A. Vanstone, “Handbook of Applied Cryptography,” CRC Press (1997)). They all differ by their choice of the set of functions. The original Diffie-Hellman key agreement protocol is an example of the above described techniques (see W. Diffie and M. E. Hellman, “New directions in cryptography,” IEEE Transaction on Information Theory, vol. IT 22 (No-vember 1976), pp. 644-654). Using an algorithm like the one first introduced by Diffie-Hellman, parties A and B can obtain a common shared secret by communicating over a public channel. The security of the system, in this instance, rests on the computational difficulty of computing discrete logarithms in the multiplicative group of the finite field. In more general cases the security is based on the notion of a one-way function. A function ƒ from a set X to a set Y is termed one-way if ƒ(x) is easy to compute for all xεX but for essentially all elements y it is computationally difficult to find xεX such that ƒ(x)=y. To date a diverse array of mathematical techniques (including geometric and algebraic ones), have been used to create systems for secure communication whose security is based on one-way functions.
A problem with some of the prior art algorithms, is that most of them rely on a cost-risk analysis when generating the one-way function. That is, in order to produce a more complex and more difficult to determine secret key, each party would need to spend more time in generating such a key and may need to invest in more expensive devices. With rapidly evolving technologies, implementing the current algorithms in a cryptographically secure manner is becoming difficult. Furthermore, there are instances of resource limited devices where current algorithms are difficult to implement. Thus, there is a need in the art for a system and method which can produce a secure key relatively quickly and without employing expensive devices.